Summary ranges

Time: O(N); Space: O(1); medium

Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

Input: nums = [0,1,2,4,5,7]

Output: [“0->2”,“4->5”,“7”]

Explanation:

  • 1,2 form a continuous range;

  • 5 form a continuous range.

Example 2:

Input: nums = [0,2,3,4,6,8,9]

Output: [“0”,“2->4”,“6”,“8->9”]

Explanation:

  • 3,4 form a continuous range;

  • 9 form a continuous range.

[11]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def summaryRanges(self, nums):
        """
        :type nums: int[]
        :rtype: str[]
        """
        ranges = []
        if not nums:
            return ranges

        start, end = nums[0], nums[0]

        for i in range(1, len(nums) + 1):
            if i < len(nums) and nums[i] == end + 1:
                end = nums[i]
            else:
                interval = str(start)
                if start != end:
                    interval += "->" + str(end)
                ranges.append(interval)
                if i < len(nums):
                    start = end = nums[i]

        return ranges

[12]:

s = Solution1()
nums = [0,1,2,4,5,7]
assert s.summaryRanges(nums) == ["0->2","4->5","7"]
nums = [0,2,3,4,6,8,9]
assert s.summaryRanges(nums) == ["0","2->4","6","8->9"]

[13]:

import itertools
import re

class Solution2:
    """
    Time: O(N)
    Space: O(N)
    """
    def summaryRanges(self, nums):
        """
        :type nums: int[]
        :rtype: str[]
        """
    def summaryRanges(self, nums):
        return [re.sub('->.*>', '->', '->'.join(repr(n) for _, n in g))
            for _, g in itertools.groupby(enumerate(nums), lambda i_n: i_n[1]-i_n[0])]

[14]:

s = Solution2()
nums = [0,1,2,4,5,7]
assert s.summaryRanges(nums) == ["0->2","4->5","7"]
nums = [0,2,3,4,6,8,9]
assert s.summaryRanges(nums) == ["0","2->4","6","8->9"]